package local;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;


public class Parser {

	static int cantOp = 0;
	
	public static void main(String[] args) {
	
		Parser parser = new Parser(); 
		File fileIn = new File("Tp3.in");
		File fileOut = new File("Tp3.out");
		File cantOp = new File("cantOp.out");
		BiGrafo big = new BiGrafo();
		FileReader frIn = null;
		FileWriter fwOut = null;
		FileWriter fwCantOp = null;
		
		try {
			frIn = new FileReader(fileIn);
			BufferedReader in = new BufferedReader(frIn);
			fwOut = new FileWriter(fileOut);
			BufferedWriter out = new BufferedWriter(fwOut);
			fwCantOp = new FileWriter(cantOp);
			BufferedWriter outOp = new BufferedWriter(fwCantOp); 


			levantoDatos(parser,in,out,outOp,big);
			System.out.println("Fin Parser...");
			
			local loc = new local(); 
			loc.solRandom(big);
			System.out.println("Fin solrandom...");
			loc.Busqlocal(big, 100);

			System.out.println("Fin Loacl...");
		} catch (IOException e) {
			System.out.println("NO SE PUDO LEER EL ARCHIVO");
			e.printStackTrace();
		} finally {
			try {
				if ( frIn != null )
					frIn.close();
			} catch (IOException e) {
				System.out.println("Error al cerrar el archivo de entrada");
			}

			try {
				if ( fwCantOp != null )
					fwCantOp.close();
			} catch (IOException e) {
				System.out.println("Error al cerrar el archivo de salida");
			}
			try {
				if ( fwOut != null )
					fwOut.close();
			} catch (IOException e) {
				System.out.println("Error al cerrar el archivo grafo");
			}
              //          return big;

		}
	}

private static void levantoDatos(Parser parser,BufferedReader br, BufferedWriter bwOut,BufferedWriter bwCantOp,BiGrafo big) throws NumberFormatException,
	IOException {
	
		int nodo;
		Integer nAux = null;
                int maxV1 = 0;
                int maxiV1 = 0;
                int maxV2 = 0;
                int maxiV2 = 0;
		// Agrego V1
		
			String sAux = br.readLine();
			
			int cantV1 = nAux.valueOf(sAux).intValue();
			
	
			for(cantV1 = cantV1;cantV1 > 0;cantV1--){
				
				sAux = br.readLine();
				nodo = nAux.valueOf(sAux).intValue();
				Node n = new Node(nodo-1,true);
                                if(n.v > maxV1)
                                {
                                    maxV1 = n.v;
                                }
				big.v1.add(n);
			}

		// Agrego V2
			sAux = br.readLine();
			int cantV2 = nAux.valueOf(sAux).intValue();
	
			for(cantV2 = cantV2;cantV2 > 0;cantV2--){
	
				sAux = br.readLine();
				nodo = nAux.valueOf(sAux).intValue();
				Node n = new Node(nodo-1,true);
                                if(n.v > maxV2)
                                {
                                    maxV2 = n.v;
                                }
				big.v2.add(n);
			}
			
		// Agrego aristas V1 a V2	
			
			sAux = br.readLine();
			int cantEjes = nAux.valueOf(sAux).intValue();
			Integer n1 = new Integer(0);
			Integer n2 = new Integer(0);
			Node nodo1 = null;
			Node nodo2 = null;
			
			for(cantEjes =cantEjes;cantEjes > 0;cantEjes--){	
				
				String[] temp = new String[2];
				temp = br.readLine().trim().split("\\s+");
				
				for(Node n :big.v1){
					if(n.v == n1.valueOf(temp[0]).intValue()-1){
						nodo1 = n;
						break;
					}
				}
				
				for(Node n :big.v2){
					if(n.v == n2.valueOf(temp[1]).intValue()-1){
						nodo2 = n;
						break;
					}
				}
				
				// Agrego el Eje
				nodo1.ady.add(nodo2);
				nodo2.ady.add(nodo1);
				
			}
		
				
		// Agrego V1' a V1
			sAux = br.readLine();
			int cantiV1 = nAux.valueOf(sAux).intValue();
	
			for(cantiV1 = cantiV1;cantiV1 > 0;cantiV1--){
	
				sAux = br.readLine();
				nodo = nAux.valueOf(sAux).intValue();
				Node n = new Node(nodo-1-big.v2.size(),false);
                                if(n.v > maxiV1)
                                {
                                    maxiV1 = n.v;
                                }
				big.iv1.add(n);
			}
                        for(Node n: big.v2)
                        {
                            n.v += big.iv1.size();
                        }
                        maxV2 += big.iv1.size();
		// Agrego V2' a V2

			sAux = br.readLine();
			int cantiV2 = nAux.valueOf(sAux).intValue();
	
			for(cantiV2 = cantiV2;cantiV2 > 0;cantiV2--){
	
				sAux = br.readLine();
				nodo = nAux.valueOf(sAux).intValue();
				Node n = new Node(nodo-1,false);
                                if(n.v > maxiV2)
                                {
                                    maxiV2 = n.v;
                                }
				big.iv2.add(n);
			}
			
		// Agrego Aristas de IV1 a IV2

                        
                        sAux = br.readLine();
			cantEjes = nAux.valueOf(sAux).intValue();
			n1 = new Integer(0);
			n2 = new Integer(0);
			nodo1 = null;
			nodo2 = null;
			
			for(cantEjes =cantEjes;cantEjes > 0;cantEjes--){	
				boolean vieneiv1 = false;
				String[] temp = new String[2];
				temp = br.readLine().trim().split("\\s+");
				if(n1.valueOf(temp[0]).intValue()-1 > maxV2)
                                {
                                    for(Node n :big.iv2)
                                    {
                                            if(n.v == n1.valueOf(temp[0]).intValue()-1)
                                            {
                                                    nodo1 = n;
                                                    break;
                                            }
                                    }
                                }
                                else if(n1.valueOf(temp[0]).intValue()-1 >(maxV1 + big.v2.size()))
                                {                                
                                    for(Node n :big.iv1)
                                    {
                                        if(n.v  == n1.valueOf(temp[0]).intValue()-1 - big.v2.size())
                                        {
                                                nodo1 = n;
                                                vieneiv1 = true;
                                                break;
                                        }
                                    }
                                }
				if(vieneiv1)
                                {
                                    if(n1.valueOf(temp[1]).intValue()-1 > maxV2)
                                    {
                                        for(Node n :big.iv2)
                                        {
                                                if(n.v == n2.valueOf(temp[1]).intValue()-1)
                                                {
                                                        nodo2 = n;
                                                        break;
                                                }
                                        }
                                    }
                                    else
                                    {
                                        for(Node n :big.v2)
                                        {
                                                if(n.v == n2.valueOf(temp[1]).intValue()-1+big.iv1.size())
                                                {
                                                        nodo2 = n;
                                                        break;
                                                }
                                        }
                                    }
                                }
                                else
                                {
                                    if(n1.valueOf(temp[1]).intValue()-1 > (maxV1+big.v2.size()))
                                    {
                                        for(Node n :big.iv1)
                                        {
                                                if(n.v == n2.valueOf(temp[1]).intValue()-1-big.v2.size())
                                                {
                                                        nodo2 = n;
                                                        break;
                                                }
                                        }
                                    }
                                    else
                                    {
                                        for(Node n :big.v1)
                                        {
                                                if(n.v == n2.valueOf(temp[1]).intValue()-1)
                                                {
                                                        nodo2 = n;
                                                        break;
                                                }
                                        }
                                    }
                                }
				// Agrego el Eje
				nodo1.ady.add(nodo2);
				nodo2.ady.add(nodo1);
                                
				
			}
                        
                        
                       // sAux = br.readLine();
                       // int cantiEjes = nAux.valueOf(sAux).intValue();
                       // int ejeN1;
                      //  int ejeN2;
                      //  for(cantiEjes = cantiEjes;cantiEjes > 0;cantiEjes--){			
                       //         String[] temp = new String[2];
                       //         temp = br.readLine().trim().split("\\s+");

                        //        ejeN1 = n1.valueOf(temp[0]);
                       //         ejeN2 = n2.valueOf(temp[1]);

                       //         int[] eje = {ejeN1 ,ejeN2};
                       //         big.iEjes.add(eje);
	}
 
}


